package com.mxw.算法之美.a9二叉树;

import com.mxw.leetcode.C1二叉树.entity.TreeNode;

import java.util.LinkedList;
import java.util.List;

/**
 * @author Administrator
 * @create 2024/7/29 10:46
 */
public class a01二叉树 {
    /**
     *  高度：节点到叶子节点的最长边数
     *  深度：根节点到某节点的边数
     *  层数：深度+1
     *
     *  满二叉树：每一层节点都是满的
     *  完全二叉树：每一层的节点都紧凑靠左排列，且除了最后一层，其他每层都必须是满的。完全二叉树的左右子树中，至少有一棵是满二叉树
     *
     *  平衡二叉树：每个节点的左右子树的高度差不超过1
     *  二叉搜索树：每个节点，其左子树的每个节点的值都要小于这个节点的值，右子树的每个节点的值都要大于这个节点的值。你可以简单记为「左小右大」。
     */

    /**
     * 链式存储
     */
    public static class Node{
        public int value;
        public Node left;
        public Node right;

        public Node(int value) {
            this.value = value;
        }
    }

    /**
     * 顺序存储： 根节点存储在数组中下标为i的位置，下标为2*i的位置为左节点，下标为2*i+1的位置为右节点，下标为i/2的位置是它的父节点。
     */

    /**
      递归遍历：时间复杂度0(n)
      框架：
     // 二叉树的遍历框架
     void traverse(TreeNode root) {
         if (root == null) {
            return;
         }
         // 前序位置
         traverse(root.left);
         // 中序位置
         traverse(root.right);
         // 后序位置
     }

     前序位置的代码会在进入节点时执行；
     中序位置的代码会在左子树遍历完成后，遍历右子树之前执行；
     后序位置的代码会在左右子树遍历完成后执行

         前序遍历：根节点->左子树->右子树
         中序遍历：左子树->根节点->右子树
         后序遍历：左子树->右子树->根节点
     */


    List<Integer> res = new LinkedList<>();

    //前序遍历结果
    List<Integer> preorderTraverse(TreeNode root) {
        preTraverse(root);
        return res;
    }

    void preTraverse(TreeNode root) {
        if (root == null) {
            return;
        }

        res.add(root.val);
        preTraverse(root.left);
        preTraverse(root.right);
    }

    void inTraverse(TreeNode root) {
        if (root == null) {
            return;
        }
        inTraverse(root.left);
        res.add(root.val);
        inTraverse(root.right);
    }


    void postTraverse(TreeNode root) {
        if (root == null) {
            return;
        }
        postTraverse(root.left);
        postTraverse(root.right);
        res.add(root.val);
    }

    /**
     层序遍历BFS ：无法知道当前节点在第几层。知道节点的层数是个常见的需求
     void levelOrderTraverse(TreeNode root) {
         if (root == null) {
            return;
         }
         Queue<TreeNode> q = new LinkedList<>();
         q.offer(root);
         while (!q.isEmpty()) {
             TreeNode cur = q.poll();
             // 访问 cur 节点
             System.out.println(cur.val);

             // 把 cur 的左右子节点加入队列
             if (cur.left != null) {
                q.offer(cur.left);
             }
             if (cur.right != null) {
                q.offer(cur.right);
             }
         }
     }

     升级版层序遍历
     void levelOrderTraverse(TreeNode root) {
         if (root == null) {
            return;
         }
         Queue<TreeNode> q = new LinkedList<>();
         q.offer(root);
         // 记录当前遍历到的层数（根节点视为第 1 层）
         int depth = 1;

         while (!q.isEmpty()) {
             int sz = q.size();
             for (int i = 0; i < sz; i++) {
                 TreeNode cur = q.poll();
                 // 访问 cur 节点，同时知道它所在的层数
                 System.out.println("depth = " + depth + ", val = " + cur.val);

                 // 把 cur 的左右子节点加入队列
                 if (cur.left != null) {
                     q.offer(cur.left);
                 }
                 if (cur.right != null) {
                     q.offer(cur.right);
                 }
             }
             depth++;
         }
     }
     */


}
